package code.c03;

import java.util.Scanner;

/**
 * @author thinkpad - 83start
 * @version v1.0
 * @create 2022/9/15 10:12
 * @package code.c03
 * @description 考虑在下面的被显示的数字金字塔（第n行第n列）。写一个程序来计算从最高点开始在底部任意处结束的路径经过数字和和的最大值。
 * 每前进一步，可以走到他的正下方，或者右下方的位置。
 * 7
 * 3 8
 * 8 1 0
 * 2 7 4 4
 * 4 5 2 6 5
 * 在上面案例中，从7 到 3 到 8 到 7 到 6 的路径产生的最大和为 30.
 */

public class MaxPath {

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        System.out.println("请输出行数：");
        int n = s.nextInt();

        // 定义二维数组
        int[][] arr = new int[n][n];
        int num = 1;

        // 初始化数组
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < num; j++) {
                System.out.println(String.format("请输入第%d行，第%d列的数字",i+1,j+1));
                arr[i][j] = s.nextInt();
            }
            num++;
        }
        // 打印数组
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                System.out.print(arr[i][j] + "\t");
            }
            System.out.println("");

        }
        // 循环遍历数组：从下往上遍历
        for (int i = n - 1; i >= 0; i--) {
            if (i == n - 1) {
                continue;
            }
            for (int j = 0; j <= i; j++) {
                // 找最大的数值
                arr[i][j] = Math.max(arr[i + 1][j], arr[i + 1][j + 1]) + arr[i][j];
            }
        }
        System.out.println("\n最大路劲和为：" + arr[0][0]);
    }
}

